package main.java.com.amanda.same;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.utils.Digraph;

import java.util.Scanner;

/**
 * @author amanda
 * @Description 基于有向图的深度优先
 */
public class DepthFirstDirectedPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public DepthFirstDirectedPaths(Digraph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        validateVertex(s);
        dfs(G, s);
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }

    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Digraph G = new Digraph(scanner);
        // StdOut.println(G);
        Scanner scanner1 = new Scanner(System.in);
        int s = scanner1.nextInt();

        DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s);

        for (int v = 0; v < G.V(); v++) {
            if (dfs.hasPathTo(v)) {
                StdOut.printf("%d to %d:  ", s, v);
                for (int x : dfs.pathTo(v)) {
                    if (x == s)
                        StdOut.print(x);
                    else
                        StdOut.print("-" + x);
                }
                StdOut.println();
            }
            else {
                StdOut.printf("%d to %d:  not connected\n", s, v);
            }

        }
    }

}
/*
13 22
4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 8 9 10 12 11 4 4 3 3 5 7 8 8 7 5 4 0 5 6 4 6 9 7 6 1 2 6 1
4
4 to 0:  4-3-2-0
4 to 1:  4-3-2-0-1
4 to 2:  4-3-2
4 to 3:  4-3
4 to 4:  4
4 to 5:  4-3-5
4 to 6:  not connected
4 to 7:  not connected
4 to 8:  not connected
4 to 9:  not connected
4 to 10:  not connected
4 to 11:  not connected
4 to 12:  not connected

8 15
4 5 5 4 4 7 5 7 7 5 5 1 0 4 0 2 7 3 1 3 2 7 6 2 3 6 6 0 6 4
 */
